#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    def wordBreak(self, s, dict):
        # write your code here
        if not dict and not s:
            return True

        if not dict:
            return False

        l = len(s)
        self.s = s
        self.dict = set(dict)
        self.max_len = max([len(ele) for ele in dict])
        self.cans = (l + 1) * [True]
        for i in range(l):
            self.cans[i+1] = self.can_break(i)
            # print('idx %s, %s' % (i, self.cans[i+1]))
        return self.cans[-1]

    def can_break(self, str_idx):
        # if self.s[0:str_idx+1] in self.dict:
        #     return True
        min_begin = max(0, str_idx + 1 - self.max_len)      # 防止出现负数

        for begin in reversed(range(min_begin, str_idx+1)):
            if self.cans[begin] and self.s[begin:str_idx+1] in self.dict:
                return True

        return False


def main():
    print("start main")
    s = Solution()
    ret = s.wordBreak('lintcode', ['lint', 'code'])
    print(ret)

if __name__ == "__main__":
    main()

